Section: New Results

Numerical computation of expectations of PDMP's

Participants : Adrien Brandejsky, Benoîte de Saporta, François Dufour.

This work concerns the computation of expectations of functionals of piecewise deterministic Markov processes (PDMP's). We propose a numerical scheme to approximate such expectations, analyze the convergence of our scheme and derive bounds for the convergence rate. More precisely, we are interested in the approximation of expectations of the form

where ${\left(X_t\right)}_{t\ge 0}$ is a PDMP, $\left(T_j\right)$ are its jump times and $l$ and $c$ are some non negative, real-valued, bounded functions. Such expectations are discussed by M.H.A. Davis in [50] , chapter 3. They often appear as cost or reward functions in optimization problems. The first term is referred to as the running cost while the second may be called the boundary jump cost. Besides, they are quite general since M.H.A. Davis shows how a wide variety of apparently different functionals can be obtained from the above specific form. For example, this wide variety includes quantities such as a mean exit time and even, for any fixed $t\ge 0$, the distribution of $X_t$ (i.e. $E_x\left[I_F\left(X_t\right)\right]$ where $F$ is a measurable set).

There are surprisingly few works in the literature devoted to the actual computation of such expectations, using other means than direct Monte Carlo simulations. M.H.A Davis showed that these expectations satisfy integro-differential equations. However, the set of partial differential equations that is obtained is unusual. Roughly speaking, these differential equations are basically transport equations with a non-constant velocity and they are coupled by the boundary conditions and by some integral terms involving kernels that are derived from the properties of the underlying stochastic process. This approach is currently under study in this project by LATP. The main difficulty comes from the fact that the domains on which the equations have to be solved vary from one equation to another making their numerical resolution highly problem specific. Another similar approach has been recently investigated in [49] , [54] . It is based on a discretization of the Chapman Kolmogorov equations satisfied by the distribution of the process ${\left(X_t\right)}_{t\ge 0}$. The authors propose an approximation of such expectations based on finite volume methods. Unfortunately, their method is only valid if there are no jumps at the boundary.

Our approach is completely different and does not rely on differential equations, but on the fact that such expectations can be computed by iterating an integral operator $G$. This operator only involves the embedded Markov chain ${(Z_n,S_n)}_{n\in N}$ and conditional expectations. It is therefore natural to propose a computational method based on the quantization of this Markov chain, following the same idea as [8] . We also addressed two important aspects that had not been investigated in [8] . The first one consists in allowing $c$ and $l$ to be time depending functions, although still Lipschitz continuous, so that we may compute expectations of the form

This important generalization has huge applicative consequences. For instance, it allows discounted cost or reward functions such as $l(x,t)=e^{-\delta t}l\left(x\right)$ and $c(x,t)=e^{-\delta t}c\left(x\right)$ where $\delta$ is some interest rate. To compute the above expectation, our strategy consists in considering, as it is suggested by M.H.A. Davis in [50] , the time augmented process ${\tilde{X}}_t=(X_t,t)$.

The second important generalization is to consider the deterministic time horizon problem. Indeed, it seems crucial, regarding to the applications, to be able to approximate

for some fixed $t_f>0$ regardless of how many jumps occur before this deterministic time. To compute this quantity, we start by choosing a time $N$ such that $P\left(T_N<t_f\right)$ be small so that the previous expectation boils down to $E_x\left[{\int }_0^{T_N}l(X_t,t)I_{\{t\le t_f\}}dt+{\sum }_{j=1}^{N}c(X_{T_j^{-}},T_j)I_{\{X_{T_j^{-}}\in \partial E\}}{I}_{\{T_j\le t_f\}}\right]$. We deal with the two indicator functions in two different ways. On the one hand, we prove that it is possible to relax the regularity condition on the running cost function so that our algorithm still converges in spite of the first indicator function. On the other hand, since the same reasoning cannot be applied to the indicator function within the boundary jump cost term, we bound it between two Lipschitz continuous functions. This provides bounds for the expectation of the deterministic time horizon functional.

An important advantage of our method is that it is flexible. Indeed, as pointed out in [47] , a quantization based method is obstacle free which means, in our case, that it produces, once and for all, a discretization of the process independently of the functions $l$ and $c$ since the quantization grids merely depend on the dynamics of the process. They are only computed once, stored off-line and may therefore serve many purposes. Once they have been obtained, we are able to approximate very easily and quickly any of the expectations described earlier. This flexibility is definitely an important advantage of our scheme over standard methods such as Monte-Carlo simulations since, with such methods, we would have to run the whole algorithm for each expectation we want to compute.

The theoretical part of this work with rigorous proofs is under review for an international peer-reviewed journal [10] . F. Dufour presented this work in an invited session at an international conference [22] .